package Offer.offer;

import domain.TreeNode;

/**
 * 重建二叉树
 *
 * @author leiwenkang
 * @date 2020/4/6
 */
public class Test06重建二叉树 {
    public static TreeNode rebuildTreeNode(int[] pre, int[] in) {
        if (pre == null || pre.length == 0
                || in == null || in.length == 0) {
            return null;
        }

        return rebuildTreeNode(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    private static TreeNode rebuildTreeNode(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        if (preStart > preEnd || inStart < inEnd) {
            return null;
        }
        int rootValue = pre[preStart];
        TreeNode root = new TreeNode(rootValue);

        //找到中序遍历中的根节点
        int index = inStart;
        for (; index <= inEnd; index++) {
            if (in[index] == rootValue) {
                break;
            }
        }
        root.left = rebuildTreeNode(pre, preStart + 1, index - inStart + preStart, in, inStart, index - 1);
        root.right = rebuildTreeNode(pre, index - inStart + preStart + 1, preEnd, in, index + 1, inEnd);
        return root;
    }
}
